1. Field
The present application relates generally to the operation of overlay networks, and more particularly, to methods and apparatus for merging peer-to-peer overlay networks.
2. Background
A network in which member nodes obtain services in the absence of server-based infrastructure is referred to herein as a “peer-to-peer overlay network” (or “p2p overlay network” or “overlay network” or simply “overlay”). Peer-to-peer overlay networks can be built on top of an underlying network, such as a network utilizing the Internet Protocol (IP). Overlay networks can consist of a few nodes to thousands of nodes joined together in a logical routing structure. Individual nodes often participate in routing and maintenance aspects of the overlay.
Typically, an overlay network is formed through an enrollment and joining process as defined by the overlay protocol. Once a node joins the overlay, it assumes ownership of some part of the routing space and performs routing functionality to enable communication among all possible pairs of nodes in the overlay. Specifically, in overlay networks based on structured DHTs (distributed hash tables), a node also assumes ownership of some part of the data items stored in the overlay.
However, overlay networks sometimes form in a disjoint manner due to the limited scope of advertisements for such networks. In such situations, it is important to merge such overlay networks into one larger overlay network so that the participating nodes in each disjoint overlay network can have access to the resources and services of a more complete set of nodes. Unfortunately, conventional systems fail to provide an efficient mechanism to merge overlay networks. For example, conventional systems typically assign new node identifiers as nodes are merged from a first overlay network to a second overlay network. This results in extensive overhead messaging and data item movement because data ownership depends on node identifiers, and changes upon merging.
Therefore, it would be desirable to have a simple and efficient mechanism that operates to allow overlay networks to merge and therefore avoid the problems associated with conventional systems.